package algo;

import model.tsp.Problem;
import model.tsp.Solution;
import util.CheckUtils;
import util.PrinterUtils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class IteratedLocalSearch extends LocalSearch3 {


    public IteratedLocalSearch(Problem problem) {
        super(problem);
    }


    /** perturbation + local search */
    @Override
    protected Solution improve(Solution initSolution) {
        int epochs = 500;
        // 迭代局部搜索过程
        Solution currentSolution = localSearch(initSolution.copy());
        for (int epoch = 0; epoch < epochs; epoch++) {
            //Solution solution = perturbation(currentSolution.copy());
            Solution solution = doubleBridgePerturbation(currentSolution.copy());
            solution = localSearch(solution);
            if (solution.getCost() < currentSolution.getCost()) {
                currentSolution = solution;
                System.out.println("第" + epoch + "次迭代：");
                PrinterUtils.printTspResult("iterated local search ", currentSolution);
            }
        }
        CheckUtils.check(currentSolution, distance);
        return currentSolution;
    }

    // 扰动
    private Solution perturbation(Solution solution) {
        int n = solution.length();
        List<Integer> newX = new ArrayList<>(solution.getPermutation());
        // 获取groupNum个index，这groupNum个index将bestSequence划分为(groupNum-1)组(并非均分)
        // n - 2的原因是：indexArr[0]和indexArr[groupNum-1]都已经确定
        int groupNum = (int) Math.round(solution.length() / 5.0);//将序列切割为若干段
        int[] indexArr = new int[groupNum];
        int elementNumInOneGroup = (n - 2) / (groupNum - 2);
        indexArr[0] = 0;
        for (int i = 1; i < indexArr.length - 1; i++) {
            indexArr[i] = random.nextInt(elementNumInOneGroup) + (i - 1) * elementNumInOneGroup + 1;
        }
        indexArr[groupNum - 1] = n;
        // 将组序打乱
        List<Integer> groupCodes = new ArrayList<>();
        for (int i = 1; i <= groupNum - 2; i++) {
            groupCodes.add(i);
        }
        Collections.shuffle(groupCodes, random);

        int index = indexArr[1];
        for (Integer code : groupCodes) {
            for (int j = indexArr[code]; j < indexArr[code + 1]; j++) {
                newX.set(index, solution.getPermutation().get(j));
                index++;
            }
        }

        return new Solution(newX, calculateFitness(newX));
    }

    private Solution doubleBridgePerturbation(Solution solution) {
        int size = solution.length();
        int a = 1 + random.nextInt(size - 2);
        int b = 1 + a + random.nextInt(size - a - 1);
        int c = 1 + b + random.nextInt(size - b);

        // path[0:a] + path[c:end] + path[b:c] + path[a:b]
        List<Integer> segment1 = solution.getPermutation().subList(0, a);
        List<Integer> segment2 = solution.getPermutation().subList(c, size);
        List<Integer> segment3 = solution.getPermutation().subList(b, c);
        List<Integer> segment4 = solution.getPermutation().subList(a, b);

        List<Integer> x = new ArrayList<>();
        x.addAll(segment1);
        x.addAll(segment2);
        x.addAll(segment3);
        x.addAll(segment4);
        return new Solution(x, calculateFitness(x));
    }
}
